On ( n , m )-chromatic numbers of graphs with bounded sparsity parameters

DOI10.1016/J.DAM.2024.07.029MaRDI QIDQ6611087zbMATH OpenFDO

Authors Sandip Das, Abhiruk Lahiri, Soumen Nandi, Sagnik Sen, S. Taruni

Publication date 26 September 2024

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

zbMATH Keywords

chromatic numbergraph homomorphismssparse graphsplanar graphspartial 2-treescolored mixed graphs

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)

Recommendations

• On coloring parameters of triangle-free planar \((n, m)\)-graphs
• On chromatic number of colored mixed graphs
• Chromatic number of sparse colored mixed planar graphs
• On clique numbers of colored mixed graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs

Cites work

• scientific article; zbMATH DE number 3904637 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 932194 (Why is no real title available?)
• Acyclic and oriented chromatic numbers of graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Chromatic number of sparse colored mixed planar graphs
• Circular chromatic number of planar graphs of large odd girth
• Colored homomorphisms of colored mixed graphs
• Complexity of conjunctive regular path query homomorphisms
• Density of 5/2-critical graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• High-girth graphs avoiding a minor are nearly bipartite
• Homomorphisms and colourings of oriented graphs: an updated survey
• Homomorphisms from sparse graphs with large girth.
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• Lower bounds for the colored mixed chromatic number of some classes of graphs.
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On acyclic colorings of planar graphs
• On chromatic number of colored mixed graphs
• On the density of \(C_7\)-critical graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Proceedings of the 64th annual IEEE symposium on foundations of computer science, FOCS 2023, Santa Cruz, CA, USA, November 6--9, 2023
• Star chromatic number
• The chromatic number of oriented graphs
• The wonderful Walecki construction
• Twin-width. I: Tractable FO model checking
• Universal targets for homomorphisms of edge-colored graphs

Cited in

(1)

• On coloring parameters of triangle-free planar \((n, m)\)-graphs

This page was built for publication: On \(( n , m )\)-chromatic numbers of graphs with bounded sparsity parameters

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