Coloring problems on bipartite graphs of small diameter

DOI10.37236/9931MaRDI QIDQ831342zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 11 May 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.11173

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

list coloringprecoloring extension problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the $k$-List Coloring, List $k$-Coloring, and $k$-Precoloring Extension problems on bipartite graphs with diameter at most $d$, proving NP-completeness in most cases, and leaving open only the List $3$-Coloring and $3$-Precoloring Extension problems when $d=3$. Some of these results are obtained through a proof that the Surjective $C_6$-Homomorphism problem is NP-complete on bipartite graphs with diameter at most four. Although the latter result has been already proved [Vikas, 2017], we present ours as an alternative simpler one. As a byproduct, we also get that $3$-Biclique Partition is NP-complete. An attempt to prove this result was presented in [Fleischner, Mujuni, Paulusma, and Szeider, 2009], but there was a flaw in their proof, which we identify and discuss here. Finally, we prove that the $3$-Fall Coloring problem is NP-complete on bipartite graphs with diameter at most four, and prove that NP-completeness for diameter three would also imply NP-completeness of $3$-Precoloring Extension on diameter three, thus closing the previously mentioned open cases. This would also answer a question posed in [Kratochv'il, Tuza, and Voigt, 2002].

Recommendations

• Hard coloring problems in low degree planar bipartite graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• Recognizing Graphs Close to Bipartite Graphs
• scientific article; zbMATH DE number 772760
• On list \(k\)-coloring convex bipartite graphs

Cites work

• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1305547 (Why is no real title available?)
• scientific article; zbMATH DE number 1156688 (Why is no real title available?)
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 772747 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A Hajós-like theorem for list coloring
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Colorings and orientations of graphs
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Covering graphs with few complete bipartite subgraphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Dominating cliques in \(P_ 5\)-free graphs
• Fall colouring of bipartite graphs and Cartesian products of graphs
• Finding vertex-surjective graph homomorphisms
• Generalized coloring for tree-like graphs
• List coloring in the absence of a linear forest
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• On the complexity of H-coloring
• Open problems on graph coloring for special graph classes
• Parameterized algorithms
• Precoloring Extension III: Classes of Perfect Graphs
• Reducibility among combinatorial problems
• Surjective \(H\)-colouring: new hardness results
• The NP-Completeness of Edge-Coloring
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition

Cited in

(5)

• Faster 3-coloring of small-diameter graphs
• Hard coloring problems in low degree planar bipartite graphs
• Coloring bipartite graphs with semi-small list size
• Partitioning \(H\)-free graphs of bounded diameter
• Injective coloring of graphs revisited

This page was built for publication: Coloring problems on bipartite graphs of small diameter

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