Search the digital library catalog

Abstract: We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph G, and Alice’s goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round i, where i = 1, 2,, … , the players are taking turns in selecting a previously unselected vertex of G and giving it color i (hence, in each round the selected vertices form an independent set). The game ends when all vertices of G are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, χig(G), of G. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus 1, and characterize the graphs in which each of the four versions of the game invariant equals 2. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large.
Keywords: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Published in DKUM: 09.08.2024; Views: 99; Downloads: 10
Full text (852,33 KB)
This document has many files! More...

Abstract: The ▫$k$▫-independence number of ▫$G$▫, denoted as ▫$alpha_k(G)$▫, is the size of a largest ▫$k$▫-colorable subgraph of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫, denoted as ▫$G times H$▫, is the graph with vertex set ▫$V(G) times V(H)$▫, where two vertices ▫$(x_1, y_1)$▫ and ▫$(x_2, y_2)$▫ are adjacent in ▫$G times H$▫, if ▫$x_1$▫ is adjacent to ▫$x_2$▫ in ▫$G$▫ and ▫$y_1$▫ is adjacent to ▫$y_2$▫ in ▫$H$▫. We conjecture that for any graphs ▫$G$▫ and ▫$H$▫, ▫$$alpha_k(G times H) ge alpha_k(G)|V(H)| + alpha_k(H)|V(G)| - alpha_k(G) alpha_k(H).$$▫ The conjecture is stronger than Hedetniemi's conjecture. We prove the conjecture for ▫$k = 1, 2$▫ and prove that ▫$alpha_k(G times H) ge alpha_k(G)|V(H)| + alpha_k(H)|V(G)| - alpha_k(G) alpha_k(H)$▫ holds for any ▫$k$▫.
Keywords: matematika, teorija grafov, neodvisnostno število, kartezični produkt grafov, mathematics, graph theory, independence number, Cartesian product of graphs
Published in DKUM: 10.07.2015; Views: 1487; Downloads: 67
Link to full text

Abstract: In the first part of my graduation thesis I speak about Latin America because that is where English Spanish cognates came from. There are twenty countries in Latin America and they generally lie south of the United States. Europeans began to influence the people and culture of Latin America with the arrival of Christopher Columbus in 1492. He "discovered" many islands in the Caribbean and mapped the coast of Central and South America. Spain built its empire in the central and southern parts of the Americas and exploited human and material resources. Preservation of Christianity in Latin America was also the goal of the Spanish Crown and it allowed colonialism to rule Latin America for over three hundred years. As I state in my graduation thesis, the Spanish domination of cruelty, exploitation, discrimination and repression did not last forever. American-born descendants of Spaniards, called criollos, fought for South American independence, and continued to rule many new nations of Spanish America for generations. The struggle for independence was hard, but despite that almost all Latin American countries had gained their independence by 1825. The main part of my graduation thesis is about English Spanish cognates. In a technical sense, cognates are two words that have a common origin. Cognates often have similar meaning, but in some cases the meaning has changed over the centuries in one language or another. An example of such a change is the English word "arena," which usually refers to a sports facility, and the Spanish arena, which usually means "sand." They both come from the Latin harena, which originally meant "sand" and came in time to also refer to an arena of a Roman amphitheater that was covered with sand. Spanish retained the meaning of "sand" (although the word can sometimes refer to a sports arena), but English expanded the word's meaning to include facilities, something like the Roman amphitheater (spanish.about.com). In a popular and not technical sense, the phrase "false cognate" is used to refer to cognates that have different meanings, such as the Spanish molestar (to bother) and the English "molest" (to abuse sexually). A more precise term to use for such word pairs is "false friends” (spanish.about.com).
Keywords: Latin America, Christopher Columbus, Spanish colonization of the Americas, Independence of Latin America, English Spanish cognates.
Published in DKUM: 03.01.2013; Views: 2001; Downloads: 118
Full text (495,92 KB)