✦ LIBER ✦

Applications of hypergraph coloring to coloring graphs not inducing certain trees

✍ Scribed by H.A. Kierstead; V. Rodl

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 385 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00187-2

No coin nor oath required. For personal study only.

✦ Synopsis

We present a simple result on coloring hypergraphs and use it to obtain bounds on the chromatic number of graphs which do not induce certain trees.

O. Introduction

A class of graphs F is said to be x-bounded if there exists a functionfsuch that for all graphs G e F, (.) z(G) <~f(og(G)), where ;t(G) is the chromatic number of G and t~(G) is the clique size of G. The class F is said to be weakly ;t-bounded if there exists a constant c such that ;t(G) <~ c, for every triangle-free graph G e F. Let G = (V, E) be a graph with X c V. Then G IX] denotes the graph induced by X in G, i.e.,

📜 SIMILAR VOLUMES

Applications of edge coloring of multigr

Applications of edge coloring of multigraphs to vertex coloring of graphs

✍ H.A. Kierstead 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 754 KB

Rado's selection principle: applications

Rado's selection principle: applications to binary relations, graph and hypergraph colorings and partially ordered sets

✍ Miroslaw Truszczynski; Zsolt Tuza 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 917 KB

Three formulations and various consequences of a compactness principle are given. For example it is shown that an infinite partially ordered set has the jump number at most k if and only if none of its finite subsets has the jump number greater than k. Other applications include Ramsey-type results

Some applications of Vizing's theorem to

Some applications of Vizing's theorem to vertex colorings of graphs

✍ Henry A. Kierstead; James H. Schmerl 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 812 KB

In this paper we shall study the relationships between the following three families of assertions: C(n): If G is a graph that does not induce & or KS-e and w(G) 6 n. then x(G)rn+l. C'(n): If M is a multigraph such that A(M)< n, p(M)<2 and M does not contain a S-sided triangle (i.e., a triangle with

Structural properties of plane graphs wi

Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

✍ O. V. Borodin 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

If in a plane graph with minimum degree 2 3 no t w o triangles have an edge in common, then: (1 there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles betw

Computer generation of king and color po

Computer generation of king and color polynomials of graphs and lattices and their applications to statistical mechanics

✍ K. Balasubramanian; R. Ramaraj 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 631 KB

A computer program is developed in Pascal for the generation of king and color polynomials of graphs. The king polynomial was defined by Motoyama and Hosoya and was shown to be useful in dimer statistics, enumera.tion of Kekule structures, etc. We show that the king polynomial of a lattice is the sa