Thinness of product graphs

DOI10.1016/j.dam.2021.04.003zbMath1485.05049OpenAlexW3158345611MaRDI QIDQ831864

Fabiano S. Oliveira, Flavia Bonomo-Braberman, Moysés S. Jr. Sampaio, Carolina Lucía Gonzalez, Jayme Luiz Szwarcfiter

Publication date: 24 March 2022

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

Full work available at URL: https://doi.org/10.1016/j.dam.2021.04.003

zbMATH Keywords

graph operationsproduct graphsthinnesscomplete thinnessindependent thinnessproper thinness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Solving problems on generalized convex graphs via mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum homomorphisms
• The fractional version of Hedetniemi's conjecture is true
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Interval-regular graphs
• An optimal greedy heuristic to color interval graphs
• Grundy number and products of graphs
• A new property of critical imperfect graphs and some consequences
• Complement reducible graphs
• Achromatic numbers and graph operations
• Optimal labelling of a product of two paths
• The complexity of comparability graph recognition and coloring
• \(k\)-tuple colorings of the Cartesian product of graphs
• The chromatic number and other functions of the lexicographic product
• Some bounds for the \(b\)-chromatic number of a graph
• Coloring graph products---a survey
• Counterexamples to Hedetniemi's conjecture
• Boxicity and cubicity of product graphs
• The \(b\)-chromatic index of direct product of graphs
• On the thinness and proper thinness of a graph
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Independence and coloring properties of direct products of some vertex-transitive graphs
• Vertex-transitive graphs
• The stable set problem and the thinness of a graph
• New Bounds on the Grundy Number of Products of Graphs
• On the b-chromatic number of some graph products
• The b -chromatic number of the cartesian product of two graphs
• Game chromatic number of Cartesian product graphs