Complexity of two coloring problems in cubic planar bipartite mixed graphs

DOI10.1016/J.DAM.2009.10.016MaRDI QIDQ968180zbMATH OpenOpenAlexFDO

Authors B. E. Eshmatov

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://doc.rero.ch/record/324396/files/coloringmixedgraphsiii.pdf

zbMATH Keywords

computational complexitybipartite graphlist coloringschedulingmixed graph coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On two coloring problems in mixed graphs
• Hard coloring problems in low degree planar bipartite graphs
• The complexity of some graph colouring problems
• Two complexity results for the vertex coloring problem
• Colouring planar mixed hypergraphs
• Mixed hypergraphs and other coloring problems
• On the complexity of bicoloring clique hypergraphs of graphs
• scientific article; zbMATH DE number 1839477
• Coloring mixed hypergraphs: theory, algorithms and applications
• Filling the complexity gaps for colouring planar and bounded degree graphs

Cites work

• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• A note on mixed tree coloring
• Coloring some classes of mixed graphs
• Complexity of Scheduling under Precedence Constraints
• Hard coloring problems in low degree planar bipartite graphs
• Mixed graph colorings
• On two coloring problems in mixed graphs
• Scheduling groups of tasks with precedence constraints on three dedicated processors.

Cited in

(5)

• Biclique-colouring verification complexity and biclique-colouring power graphs
• Parameterized mixed graph coloring
• On the complexity of the selective graph coloring problem in some special classes of graphs
• Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
• On two coloring problems in mixed graphs

This page was built for publication: Complexity of two coloring problems in cubic planar bipartite mixed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968180)