Complexity of two coloring problems in cubic planar bipartite mixed graphs

DOI10.1016/j.dam.2009.10.016zbMath1226.05122OpenAlexW2093519478MaRDI QIDQ968180

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 complexityschedulingbipartite graphlist coloringmixed graph coloring

Mathematics Subject Classification ID

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

Related Items (3)

Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ Parameterized mixed graph coloring ⋮ On the complexity of the selective graph coloring problem in some special classes of graphs

Cites Work

• Unnamed Item
• Coloring some classes of mixed graphs
• A note on mixed tree coloring
• Mixed graph colorings
• Scheduling groups of tasks with precedence constraints on three dedicated processors.
• On two coloring problems in mixed graphs
• Hard coloring problems in low degree planar bipartite graphs
• Complexity of Scheduling under Precedence Constraints

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