Computer Science – Discrete Mathematics
Scientific paper
2009-04-29
Computer Science
Discrete Mathematics
24 pages, 1 figure Corrected the statements of Lemma 4.3 and 4.4
Scientific paper
A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. The instances of the Weighted Maximum H-Colourable Subgraph problem (MAX H-COL) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=K_k this problem is equivalent to MAX k-CUT. Farnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of MAX H-COL. Specifically, it can be used to extend previously known (in)approximability results to larger classes of graphs. Here, we investigate the properties of this parameter on circular complete graphs K_{p/q}, where 2 <= p/q <= 3. The results are extended to K_4-minor-free graphs and graphs with bounded maximum average degree. We also consider connections with Samal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.
Engström Robert
Färnqvist Tommy
Jonsson Peter
Thapper Johan
No associations
LandOfFree
Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-512054